home *** CD-ROM | disk | FTP | other *** search
/ Aminet 19 / Aminet 19 (1997)(GTI - Schatztruhe)[!][Jun 1997].iso / Aminet / demo / mag / trash3_2.lha / fuentes / Phornee_Dum4k.lha / Phornee.Dum_de_4k.DOC
Text File  |  1991-10-01  |  30KB  |  704 lines
  1.  
  2. *************************************** ©PHORNEE/GOBLINS ********************************************
  3. En espaÑol, ¡joder!... ya era hora....
  4. Nota: Si alguien no entiende eso de "blitter", "copper", etc, que se aguante y se vaya a jugar
  5. con su videoconsola 486 (para su vergüenza... el hermano pequeño del pentium.)
  6.  
  7. Como hacer un laberinto 3D tipo Doom-Wolfstein en 5 minutos... (je,je)
  8.  
  9. PRELIMINAR
  10. ==========
  11.  
  12. Para tratar números decimales con maxima eficiencia, es recomendable trabajar con un sistema de
  13. coma fija (16:16) (bits, claro!)
  14. Sin & Cos:   Despues de todo el rollo, veras que no son necesarias tablas de senos.
  15. Tan & Cotan: 16 entero 16 decimales
  16. Cosec & Sec: 16 entero 16 decimales
  17. Angulos:     0-2¶ ===> 0-2047
  18. Así evitaré toda llamada al S.O para manejo de coma flotante, y manejar decimales será casi tan rápido
  19. como hacerlo con enteros. No se harán llamadas a la mathieeedoubbas.library.
  20. Ademas, con la inclusión de tablas precalculadas de las razones trigonométricas, se evitarán llamadas
  21. a la mathieeedoubtrans.library.
  22. Aqui se exponen los algoritmos de proyección de rayos... el dibujo en pantalla de las paredes va de 
  23. vuestra cuenta.
  24. Se intentará que los accesos a memoria sean mínimos, y la inmensa mayoría de las instrucciones serán
  25. operaciones con registros. 
  26. Asimismo, será preferible usar codigo especial para 68020+, ya que esto acelera los acessos a tablas
  27. Longword & Word.
  28. Ademas, dado el nivel de anidamiento de los algoritmos y comparaciones, sería MUY conveniente usar
  29. algún tipo de macros para dotar al ensamblador de WHILEs,UNTILs,REPEATs,IF-THEN-ELSEs,etc..
  30. (Lo mejor es que utilices el "PhDefs" que yo hize a tal efecto. ¿Quién necesita el 'C' ahora?).
  31.  
  32. NUESTRO LABERINTO.....................
  33. =======================================
  34.  
  35. Visión de la Planta del laberinto.
  36.  
  37. Cada bloque es de 256x256 puntos.
  38.     .      .       .       .        .       .
  39.     .      .       .       .        .       .
  40. --------........--------........----------------
  41. |bloque|........|bloque|........|bloque||bloque|
  42. |      |........|      |........|      ||      | ...    Los bloques marcados con puntos, se supone
  43. | 0,3  |........| 2,3  |........| 4,3  || 5,3  |        que son bloques "vacios", sin pared.
  44. --------........--------........----------------
  45. ........--------................--------........        Cada bloque de pared, tiene cuatro valores,
  46. ........|bloque|................|bloque|........        uno para cada dirección (arriba,derecha...)
  47. ........|      |................|      |........ ...    Esto permitirá que un bloque sólido,tenga cada
  48. ........| 1,2  |................| 4,2  |........        pared de una textura diferente. Asi pues,
  49. ........--------................--------........        cada bloque solido tiene 4 paredes.
  50. ................................................
  51. ................................................        Mi laberinto será de 256*256 bloques, donde
  52. ................................................        cada bloque es de 256*256 puntos (<>pixeles)
  53. ................................................ ...    Asi cabe todo en una matriz bidimensional
  54. ................................................        de (Word*Word).
  55. --------........--------........................
  56. |bloque|........|bloque|........................        El observador(*) estará en una coord.(Ox,Oy)
  57. |      |........| del *|........................ ...    (0..65535,0..65535), por lo cual estará sito
  58. | 0,0  |........|observ|........................        en el bloque (Ox/256,Oy/256).
  59. --------........--------........................
  60.                                     ¿Que coño debemos dibujar en la pantalla?.
  61. Debemos dibujar, lo que vea el observador.El observador ó cámara, además de estar en una determinada
  62. posición (Ox,Oy), estará  mirando hacia una dirección en concreto.
  63. Esta dirección la llamaremos ß. ß es un ángulo. Además de eso, tenemos que definir el espectro o 
  64. 'diafragma' de visión del observador. La cámara ve en un entorno alrededor de su direccion de
  65. mirada. Este "diafragma" lo llamaremos Angß (Incremento de ß). Un ejemplo:
  66.  
  67.             /n                                                        DIRECCION DE ANGULOS
  68.            /ó       * = observador                                            90°
  69.           /i                                                                   |  
  70.          /c         ...... origen de los ángulos (ángulo 0)                    |
  71.         /c                                                          180° ------+------ 0°
  72.        /e           /  dirección donde mira el observador.                     |
  73.       /r                                                                       |
  74.      /i \ ß         ß ángulo que define la dirección de mirada en mapa 2D.    270°
  75.     /D   \
  76.    *................
  77.  
  78. Aqui trato los angulos en grados (°), para aclararme mejor, pero en implementación, usare 2048
  79. divisiones para 2¶ radianes (360°).
  80.               
  81. Imaginemos que ß es igual a 0 (Mirando completamente a la derecha del mapa 2D), y que Angß vale 45°:
  82.                  ...................
  83.                /....................
  84.               /.....................
  85.              /......................   ...     La región que el observador "ve", es la marcada
  86.             /.\.Angß................         con puntos. Asi pues, es la zona delimitada por
  87.            /...\....................             los ángulos ß-Angß y ß+Angß
  88.           *-------------------- ß...   ...
  89.            \.../....................
  90.             \./.Angß................                   PLANTA DEL LABERINTO
  91.              \......................   ...       ©---------------------- EJE X
  92.               \.....................             |##############
  93.                \....................             |#.#......#..
  94.                  ...................             |#.#.####.#.        © representa el eje Y saliendo
  95.                                                  |#..........              desde la pantalla.
  96.                          .                       |######.###.          # son bloques sólido
  97.                           .                      |........... 
  98.                            .                     |                 . son "pasillos" (ausencia de
  99.                                        EJE Z                           bloque solido)
  100.                          
  101. COMO PROYECTAR EN PSEUDO 3D
  102. ===========================
  103.  
  104. Aqui comienza el cotarro. El rollo está en que las paredes sólo giran en el eje Y. Asi pues, como 
  105. todas las paredes son verticales si hallamos si una pared se ve o no para una Y generica, ya sabremos
  106. si se ve o no para todas sus Ys.
  107. Asi pues, si efectuamos la visión de la planta del laberinto (Olvidandonos asi de la 3D), y hacemos
  108. los calculos sin tener en cuenta la Y, todo se simplifica un montón, y luego no será dificil plasmarlo
  109. en 3D en la pantalla.
  110.  
  111. A partir de ahora, y hasta que no se diga lo contrario, estamos hablando del mapa en 2D.
  112.  
  113. Consideremos que la pantalla es de 320 puntos de anchura. Si trazamos 320 rayos horizontales desde el
  114. observador hacia el laberinto, y anotamos con qué pared choca, obtendríamos un vector lineal, que nos
  115. diría que bloque exactamente se ve en cada X fisica de la pantalla. Fijate un poco, y verás que para
  116. una columna en concreto de la pantalla, sólo se ve una pared. Y esa pared, deberá ser precisamente de
  117. la textura que hemos encontrado para esa X, al trazar el rayo. Hasta aqui parece que no va a ser
  118. muy dificil. Pero sigamos...
  119.  
  120. Ahora, consideremos que nuestra pantalla es de NumDiv pixeles de ancho. Para cubrir la pantalla
  121. entera, necesitaremos lanzar (en principio... ya veremos, ya...) NumDiv rayos. Estos rayos deben
  122. cubrir todo el espectro de vision o diafragma del observador, asi es que deberan ir desde ß-Angß
  123. hasta ß+Angß. Llamemos ß0 a ß-Angß. Hallamos la diferencia de cada uno de los NumDiv ángulos entre
  124. si, y lo llamaremos ðß (incremental de ß). ðß = [(ß+Angß) -  (ß-Angß)] / NumDiv = 2*Angß / NumDiv
  125. El primero de los rayos a trazar, es ß0. El segundo es ß0+ðß. El tercero es ß0+2*ðß...ß0+3*ðß...
  126. ... ß+(NumDiv-1)*ðß. Todos ellos, son ángulos a trazar. Asi pues, para cada columna de la pantalla,
  127. lanzaremos un rayo.
  128. Este sistema de trazar rayos con divisiones angulares, ocasionará seguramente una deformación 
  129. cilindrica en los extremos horizontales de la pantalla. Si queda mal, habra que arreglarlo haciendo
  130. una división lineal del plano de proyección. (Ayer hize los calculos en clase de Redes, porque me
  131. aburría... Los pondré al final, si no queda bien con ángulos). Pero bueno, así es como ve el ojo
  132. real, lo que pasa es que no percibimos la deformación, porque vemos casi exclusivamente con el centro
  133. del ojo, donde la deformación es mínima. Bueno, creo que estoy divagando otra vez...
  134.  
  135. MEJORA
  136. ======
  137.  
  138.  ¡¡Revelacion!!. Ya no necesitaremos trazar los 320 rayos.Lanzaremos el rayo inicial,ß0 para encontrar
  139. la primera pared.(La del extremo izquierdo del campo de visión). Pero cuando hayamos encontrado esa
  140. pared,podemos lanzar otro rayo directamente a la esquina final de la pared (øN). Este øN es el angulo
  141. real a la esquina final de la pared, y no tiene por que coincidir con ninguno de los ß (es más,
  142. seguro que no coincide). Recordemos que tenemos un número finito de ßs.(P.ej: 320).Si el rayo lanzado
  143. choca realmente con la pared antes encontrada,ya sabemos que entre el angulo del rayo inicial, y el 
  144. segundo rayo a la esquina, SOLO hay una pared,(ESA pared),y no necesitaremos lanzar mas rayos para esa
  145. pared,ahorrandonos bastantes operaciones.
  146. Si el segundo rayo (a la esquina) no chocase con nuestra pared, sino con otra mas cercana al observador
  147. ,se podria hacer un tratamiento recursivo similar para esta nueva pared, y devolver el principio de
  148. esta segunda pared, como final de la primera.
  149. Luego se lanzaría otro rayo buscador, para encontrar la siquiente pared a la derecha. Ese rayo seria
  150. aquel de la serie ß, posterior al øN real de la última pared.
  151.  
  152. Asi pues, devolveremos como resultado una lista. Cada nodo de la lista contendrá la información
  153. suficiente para dibujar una pared (o cacho de pared), en orden de izquierda a derecha. La estructura
  154. de todas las paredes, o pedazos de pared, será la de un trapecio tumbado.
  155.  
  156.                  ß Inic          ß Final             Estos ßs son dos de los "320" ßs.
  157.                      .             .
  158.                      .             .
  159.                      .             .
  160.                      .            /| ...
  161.                      .         /   |   .
  162.                      .      /      |   .
  163.                      .   /         |   .
  164.                      ./            |   .
  165.                   ...|             |   .
  166.              AP   .  |             |   AP           Estas AP (Alturas proyectadas) son función
  167.           Inicial ...|             | Final        directa de las Zs de los extremos de la pared.
  168.                       \            |   .
  169.                          \         |   .
  170.                             \      |   .
  171.                                \   |   .
  172.                                   \| ...
  173.  
  174. --------------------------------
  175. | ß Inicial     | ß Final      |
  176. |---------------+--------------|
  177. | Z Inicial     | Z Final      |
  178. |---------------+--------------|
  179. | InicioTextura | FinalTextura |
  180. |---------------+--------------|
  181. | BloqueX        | BloqueY      |
  182. ----------------+---------------
  183. | Dirección     |
  184. -----------------
  185.  
  186. **************
  187. *PSEUDOCODIGO*
  188. **************
  189.  
  190. Main
  191. ¯¯¯¯
  192. ø=0;                        /*Mirando a la derecha*/
  193. Angß=255;                    /*45°*/
  194. ß=ø-Angß;                    /*ß=ß0*/
  195. Punt=0;                        /*Primer nodo*/
  196. DO_WHILE
  197.     TrazarBuscador(ß);            /*Encuentra pared e inicializa Pared(Punt)*/
  198.     ß=TrazarVerificador(&Pared[Punt]);    /*Completa Pared*/
  199.     ß=ß+ðeltaß
  200. WHILE ß<ø+Angß;
  201.  
  202. Punt=Punt-1;
  203. Dß=ø+Angß-Pared[Punt].ßInicial;
  204. DP=Pared[Punt].ßFinal-Pared[Punt].ßInicial;
  205. DZ=Pared[Punt].ZFinal-Pared[Punt].ZInicial;
  206. Pared[Punt].ZFinal=Dß*DZ/DP
  207. Pared[Punt].ßFinal=ø+Angß;
  208.  
  209.  
  210. COMO PROYECTAR UN RAYO GENERICO
  211. ===============================
  212. Vamos a dividir el espectro de ángulos en ocho sectores (octantes):
  213.  
  214.                         90°                     DIRECCIONES DE CHOQUE
  215.                 135°     |       45°       
  216.                   \   3  |  2   /                Arriba=0
  217.                     \    |    /                      |
  218.                 4     \  |  /     1                  |
  219.                         \|/                      |
  220.         180°-------------+------------- 0°    Izqui=3     ---------+--------- Derecha=1
  221.                         /|\                      |
  222.                 5     /  |  \      8                  |
  223.                     /    |    \                      |
  224.                    /  6  |  7   \                Abajo=2
  225.                  225°    |       315°
  226.                         270°
  227.                         
  228. Los valores HAD (Exahustivo Horizontal/ Arriba/ Derecha) son bits usados para mayor rapidez en
  229. condiciones de comparación con octantes.
  230. H vale 1, si el coseno es mayor que el seno.(MSB2=MSB3)
  231. A vale 1, si el seno es positivo. (MSB1=0)
  232. D vale 1, si el coseno es positivo. (MSB1=MSB2)
  233.  
  234.           VALORES DE HAD             VALORES DE MSB DE ANGULOS (rango 2048) LSB=x=8 bits
  235.                          90°                                        |
  236.                 135°     |       45°                      \  010x  |  001x  /
  237.                   \  010 |  011 /                           \      |      /
  238.                     \    |    /                                  \    |    /
  239.                110    \  |  /    111                   011x     \  |  /    000x
  240.                         \|/                                      \|/
  241.         180°-------------+------------- 0°     ------------------+----------------
  242.                         /|\                              /|\
  243.                100    /  |  \     101                  100x     /  |  \    111x
  244.                     /    |    \                          /    |    \
  245.                   /  000 |  001 \                    /      |      \
  246.                 225°     |       315°                     /  101x  |  110x  \
  247.                         270°                                       |
  248.  
  249. Ahora tomemos un rayo en particular. Será un rayo con dirección ø. Debemos seguir con
  250. atención su recorrido para ver con que pared choca. (Si se hace recursivamente, sería trivial hacer
  251. texturas especulares. ¡Ostias, que guapo!. Ya veremos, ya...). Para ello, testearemos todos los
  252. bloques del laberinto que el rayo cruza, empezando desde el bloque en que se encuentra el Observador.
  253. Cuando encontremos el primer bloque de ésta trayectoria, que es sólido, habremos tocado pared.
  254. El bloque inicial,como ya hemos dicho,será el (Ox/256,Oy/256).Lo llamaremos B = (BOx,BOy).
  255. Lo primero que debemos saber,es por qué lado (de los cuatro) de dicho bloque, sale el rayo...
  256.  
  257.  LADO VERTICAL DEL BLOQUE (BOx,BOy)          Como vamos a recorrer los bloques uno a uno desde el
  258.   ----------------------------  /            bloque del *, necesitamos trazar una de las dos 
  259. L |                     .    | /             trayectorias posibles, ya que sólo una de ellas es
  260. A |                     .    |/              adecuada.
  261. D |               OffY  .    y                        #                 o#
  262. O |                     .   ry                        o                 o
  263.   |                     .  r y <= sen(ø)*r           oo   ó bien       oo      "o" es el rayo
  264. H |                     . r  y                       o                 o
  265. O |     Offx            .r   y                      *o                 *
  266. R |.....................*xxxxy...........    Donde * es el bloque del observador, y # es el primer
  267. I |                        ^ |                 bloque impactado por el rayo. En el primer caso, el
  268. Z |                  cos(ø)*r|               rayo choca con la pared de abajo del bloque. En el
  269.   ----------------------------               segundo, choca con la pared izquierda.
  270.   
  271. Para diferenciar las dos trayectorias, debemos saber por cual de los cuatro lados dentro del bloque
  272. de la camara, sale el rayo hacia su destino. Es mas... sólo nos interesará saber, si sale horizontal
  273. o verticalmente. Tenemos pues, el rayo de angulo ø, y la posicion del observador (Ox,Oy).
  274. Hallemos el offset del observador dentro de su bloque:
  275. OffsetX= Ox-BOx*256     +(0..255)
  276. OffsetY= Oy-BOy*256     +(0..255)
  277.                                                                       
  278. a) Cuadrante 1 (Correspondiente a la figura de arriba) 0 <= ø < 90   |    HAD=x11
  279.     cos(ø)*radio=(255-OffsetX)  ===>  radio=(255-OffsetX)/cos(ø)     |___
  280.     El rayo saldrá por el lado horizontal derecho si:
  281.     sen(ø)*radio < (255-OffsetY) ===> (255-OffsetX)*Tg(ø)-(255-OffsetY) < 0 ...si no, sale por abajo.
  282.     
  283. b) Cuadrante 2     90 <= ø < 180                        
  284.     -cos(ø)*radio=OffsetX  ===> radio=-OffsetX/cos(ø)       |    HAD=x10
  285.     El rayo saldrá por el lado horizontal izquierdo si:  ___|
  286.     sen(ø)*radio < (255-OffsetY) ===> -OffsetX*Tg(ø)-(255-OffsetY) < 0 ... si no, sale por abajo
  287.                                                               ___
  288. c) Cuadrante 3   180 <= ø < 270                                  |    HAD=x00
  289.     -cos(ø)*radio=OffsetX  ===>  radio=-OffsetX/cos(ø)           | 
  290.     El rayo saldrá por el lado horizontal izquierdo si:
  291.     -sen(ø)*radio < OffsetY ===> OffsetX*Tg(ø)-OffsetY < 0 ...si no, sale por arriba.
  292.                                                                      ___
  293. d) Cuadrante 4     270 <= ø < 360                                   |
  294.     cos(ø)*radio=OffsetX  ===> radio=(256-OffsetX)/cos(ø)           |        HAD=x01
  295.     El rayo saldrá por el lado horizontal derecho si:
  296.     -sen(ø)*radio < OffsetY ===>-(255-OffsetX)*Tg(ø)-OffsetY < 0 ... si no, sale por arriba
  297.  
  298. Ahora ya sabemos cual de los dos caminos tenemos que coger. Debemos hallar ahora una forma de recorrer
  299. todos los cuadros hasta chocar con algo.
  300.                       
  301. En los sectores 1,4,5,8, |Tg(ø)| es menor o igual a 1. La Tg se puede interpretar como: (toma
  302. carrerilla...) "lo que hay que aumentar la y, por cada unidad que aumente la x".
  303. Asimismo, la Cotg es "lo que hay que aumentar la x, por cada unidad de y que añada".
  304. En los sectores 2,3,6,7, es la |Cotg(ø)| la que es menor o igual que 1. 
  305.  
  306. Que en los octantes la |Tg| o la |Cotg| sea menor que uno, es importante, ya que queremos trazar un
  307. camino "continuo". Si fuese mayor que uno, nos saltaríamos algun bloque sin testear. Si no entiendes
  308. ni "j", mira los parrafos siguientes.
  309.  
  310. *) Supongamos que nuestro ángulo es 1,4,5 u 8. Lo que debemos hacer, es incrementar
  311.  (o decrementar) la x de uno en uno, y por cada vez que lo hagamos, aumentaremos la y por el valor de
  312.  Tg(ø). Además, deberemos hacerlo de una forma alternativa, es decir:
  313.  a) x=x±1;       TestearBloque (x,y)  (+1 si 1 u 8, y -1 si 4 o 5)
  314.  b) y=y±Tg(ø);   TestearBloque (x,y)  (+ si 1 u 8, y - si 4 o 5)
  315.  c) x=x±1;       TestearBloque (x,y)
  316.  d) y=y±Tg(ø);   TestearBloque (x,y)
  317.  .
  318.  .
  319.  . seguir asi hasta que el test resulte positivo (mas de 0.6, multa por embriaguez, je,je,je).
  320.  Eso en el caso de que el rayo saliese del (BOx,BOy) por una pared horizontal. Si el rayo saliese
  321.  por una pared vertical, deberiamos añadir un paso inicial:
  322.  0) y=y±Tg(ø);   TestearBloque (x,y)
  323.  
  324. *) Si el ángulo es 2,3,6,7...
  325.  a) y=y±1;       TestearBloque (x,y) (+1 si 2 o 3, y -1 si 6 o 7)
  326.  b) x=x±Cotg(ø); TestearBloque (x,y) (+ si 2 o 3, - si 6 o 7)
  327.  c) y=y±1;       TestearBloque (x,y)
  328.  d) x=x±Cotg(ø): TestearBloque (x,y)
  329.  .
  330.  .
  331.  . seguir asi hasta chocar.
  332.  Eso si el rayo saliese de (BOx,BOy) por una pared vertical. Si saliese horizontalmente, habría que
  333.  añadir un nuevo paso al principio:
  334.  0) x=x±Cotg(ø); TestearBloque (x,y)
  335.  
  336. Resumiendo...
  337.                          |        
  338.                 \  Cot(ß)|Cot(ß)  /          ðx
  339.                   \   1  |  1   /        ðy
  340.                 -1  \    |    /      1    
  341.              -Tg(ß)   \  |  /   Tg(ß)  
  342.                         \|/        
  343.         180°-------------+------------- 0°
  344.                 -1      /|\      1    
  345.              -Tg(ß)   /  |  \   Tg(ß)        
  346.                     /    |    \          
  347.                   /      |      \    
  348.                 / -Cot(ß)|-Cot(ß) \
  349.                      -1  |  -1
  350.  
  351.   Tiene pintas de ser rapido. La Tg y Cotg es la misma para todos los pasos
  352. de un mismo rayo, y no hay multiplicaciones ni divisiones. Ya veremos...
  353.  
  354.  Nota: TestearBloque, entre otras cosas, debería anotar en algún sitio la dirección de choque, y
  355.  la x e y del bloque de choque, para cálculos posteriores.
  356.  
  357. **************
  358. *PSEUDOCODIGO*
  359. **************
  360.  
  361. TrazarRayo(µ,&Result)
  362. ¯¯¯¯¯¯¯¯¯¯
  363. HAD=HallarHAD(µ);
  364. BOx=Ox/256;
  365. BOy=Oy/256;
  366. OffsetX= Ox-BOx*256
  367. OffsetY= Oy-BOy*256
  368.  
  369. CASE µ OF
  370.     CASE PrimerCuadrante entonces    /*HAD=x11*/
  371.         Si ((255-OffsetX)*Tg(µ)-(255-OffsetY) < 0) entonces salida=horizontal
  372.                                     sino     salida=vertical
  373.     CASE SegundoCuadrante entonces    /*HAD=x10*/
  374.         Si (-OffsetX*Tg(µ)-(255-OffsetY) < 0) entonces salida=horizontal
  375.                                   sino     salida=vertical
  376.     CASE TercerCuadrante entonces    /*HAD=x00*/
  377.         Si (OffsetX*Tg(µ)-OffsetY < 0) entonces salida=horizontal
  378.                            sino     salida=vertical
  379.     CASE CuartoCuadrante entonces    /*HAD=x01*/
  380.         Si (-(255-OffsetX)*Tg(µ)-OffsetY < 0) entonces salida=horizontal
  381.                               sino     salida=vertical
  382. END_CASE
  383.      
  384. Si (octante=1 ó octante=4 ó octante=5 ó octante=8) entonces /*HAD=1xx*/
  385.         {
  386.         Si (salida=vertical) entonces
  387.                 {
  388.                 BOy=BOy+Tg(µ)±1;    dependiendo del ángulo
  389.                 Si (Mapa(BOx,BOy)<>0) entonces
  390.                     {
  391.                     Si Tg(µ)>0 entonces *Result.Direc=arriba
  392.                            sino     *Result.Direc=abajo
  393.                     GOTO CHOQUE
  394.                     }
  395.                 }
  396.         Si (octante=1 ó octante=8) entonces ðBx=1    /*HAD=xx1)*/
  397.                        sino     ðBx=-1
  398.         DO_WHILE 1=1
  399.             BOx=BOx+ðBx;
  400.             Si (Mapa(BOx,BOy)<>0) entonces
  401.                     {
  402.                     Si ðBx=1 entonces *Result.Direc=derecha
  403.                              sino      *Result.Direc=izquierda
  404.                     GOTO CHOQUE
  405.                     }
  406.             BOy=BOy+Tg(µ);
  407.             Si (Mapa(BOx,BOy)<>0) entonces 
  408.                     {
  409.                     Si Tg(µ)>0 entonces *Result.Direc=arriba
  410.                            sino     *Result.Direc=abajo
  411.                     GOTO CHOQUE
  412.                     }
  413.         END_WHILE
  414.         }
  415.     sino
  416.         {
  417.         Si salida=horizontal entonces
  418.                 {
  419.                 BOx=BOx+Cotg(µ)±1;    dependiendo del ángulo
  420.                 Si (Mapa(BOx,BOy)<>0) entonces
  421.                     {
  422.                     Si Cotg(µ)>0 entonces *Result.Direc=derecha
  423.                              sino     *Result.Direc=izquierda
  424.                      GOTO CHOQUE
  425.                      }
  426.                 }
  427.         Si (octante=2 ó octante=3) entonces ðBy=1    /*HAD=x1x*/
  428.                        sino     ðBy=-1
  429.  
  430.         DO_WHILE 1=1
  431.             BOy=BOy+ðBy;
  432.             Si (Mapa(BOx,BOy)<>0) entonces 
  433.                     {
  434.                     Si ðBy=1 entonces *Result.Direc=arriba
  435.                              sino      *Result.Direc=abajo
  436.                     GOTO CHOQUE
  437.                     }
  438.             BOx=BOx+Cotg(µ);
  439.             Si (Mapa(BOx,BOy)<>0) entonces
  440.                     {
  441.                     Si Cotg(µ)>0 entonces *Result.Direc=derecha
  442.                              sino     *Result.Direc=izquierda
  443.                      GOTO CHOQUE
  444.                      }
  445.         END_WHILE
  446.         }
  447. CHOQUE:        *Result.Bloque=(BOx,BOy);
  448.  
  449.  
  450. COMO PROYECTAR UN RAYO BUSCADOR
  451. ===============================
  452.  
  453.  Ya sabemos trazar un rayo generico. Veamos ahora como trazar un RayoBuscador, que dado un angulo,
  454. nos devuelva, ademas de el Bloque y la dirección de choque, el offset de la textura y la distancia
  455. del observador a el punto de impacto (Z).
  456.  
  457. a) Si el rayo ha chocado hacia arriba...
  458.  
  459.   i) 90 < ø < 180                    ##############      Cotg(ø)= -
  460.   Dy=(By*256)-Oy                             |\         Dy= +
  461.   Dx=Dy*Cotg(ø)                              | \         Dx= + * - = -
  462.                                           Dy |  \__      Cosec(ø)= +
  463.                                              |   \ \ ø
  464.                                              |....*.\.....
  465.                                       xxxxxxx  Dx  
  466.                                               
  467.     DTextur=Ox-(Bx*256)+Dx        DTextur= desplazamiento dentro de Textura
  468.     Z=Dy*Cosec(ø)                 Z= distancia del observador al punto de choque
  469.   
  470.   ii) 0 < ø < 90        Cotg(ø)= +
  471.   Dy=(By*256)-Oy                Dy=+
  472.   Dx=Dy*Cotg(ø)                 Dx= + * + = +
  473.                                 Cosec(ø)= +
  474.     DTextur=Ox-(Bx*256)+Dx   
  475.     Z=Dy*Cosec(ø)            
  476.   
  477.   Se puede ver que no hay que diferenciar en octantes, ya que la expresión coincide. Es decir; si
  478.   hemos chocado hacia arriba, nos da igual en que cuadrante esté el ángulo.
  479.  
  480. b) Si el rayo ha chocado hacia abajo...
  481.  
  482.    Dy=Oy-((By+1)*256)        Dy=+
  483.    Dx=Dy*Cotg(ø)
  484.  
  485.      DTextur=((Bx+1)*256)-Ox+Dx
  486.      Z=-Dy*Cosec(ø)
  487.    
  488. c) Si el rayo ha chocado hacia la derecha...
  489.  
  490.    Dx=(Bx*256)-Ox               Dx=+
  491.    Dy=Dx*Tg(ø)                 
  492.    
  493.      DTextur=((By+1)*256)-Oy+Dy
  494.      Z=Dy*Cosec(ø)
  495.  
  496. d) Si el rayo ha chocado hacia la izquierda...
  497.  
  498.    Dx=Ox-((Bx+1)*256)           Dx=+
  499.    Dy=Dx*Tg(ø) 
  500.    
  501.      DTextur=-(By*256)-Oy+Dy
  502.      Z=-Dy*Cosec(ø)
  503.     
  504. **************
  505. *PSEUDOCODIGO*
  506. **************
  507.  
  508. TrazaBuscador (µ)
  509. ¯¯¯¯¯¯¯¯¯¯¯¯¯
  510. Pared[Punt].ßInicial=µ;        /*Esta pared,SEGURO que empieza en este ángulo*/ 
  511. TrazarRayo(µ,&Pared[Punt]);
  512. CASE Pared[Punt].Direc OF
  513.     CASE Arriba entonces 
  514.             {
  515.               Dy=(Pared[Punt].By*256)-Oy;
  516.             Dx=Dy*Cotg(µ);
  517.             Pared[Punt].InicioTextura=Ox-(Pared[Punt].Bx*256)+Dx;
  518.             Pared[Punt].ZInicial=Dy*Cosec(µ);
  519.             }
  520.     CASE Abajo entonces 
  521.             {
  522.             Dy=((Pared[Punt].By+1)*256)-Oy;
  523.             Dx=Dy*Cotg(µ);
  524.             Pared[Punt].InicioTextura=((Pared[Punt].Bx+1)*256)-Ox+Dx;
  525.             Pared[Punt].ZInicial=Dy*Cosec(µ);
  526.             }
  527.     CASE Izquierda entonces 
  528.             {
  529.             Dx=((Pared[Punt].Bx+1)*256)-Ox;
  530.             Dy=Dx*Tg(µ);
  531.             Pared[Punt].InicioTextura=Oy-(Pared[Punt].By*256)+Dy;
  532.             Pared[Punt].ZInicial=Dx*Sec(µ)            
  533.             }
  534.     CASE SI_OTRO entonces    /*derecha*/ 
  535.             {
  536.             Dx=(Pared[Punt].Bx*256)-Ox
  537.             Dy=Dx*Tg(µ);
  538.             Pared[Punt].InicioTextura=((Pared[Punt].By+1)*256)-Oy+Dy;
  539.             Pared[Punt].ZInicial=Dx*Sec(µ);
  540.             }
  541. END_CASE
  542.  
  543.  
  544.      
  545.  
  546. COMO PROYECTAR UN RAYO VERIFICADOR
  547. ==================================
  548.  
  549. Dado el observador, un bloque y una dirección, verifica si el rayo que une el observador, con el
  550. final de la pared correspondiente, choca realmente con dicha pared, o si hay algún obstaculo delante.
  551. a) Si choca con la misma pared, devolverá el ß correspondiente a la esquina.
  552. b) Si choca con otra distinta de la pared esperada, realizará una llamada recursiva con la
  553.   nueva pared, y finalmente devolvera el último ß.
  554. Esta funcion recibe un nodo de pared parcialmente actualizado:
  555. (ßInicial,Bloque,Direc,InicioTextura,ZInicial)
  556.  
  557. **************
  558. *PSEUDOCODIGO*
  559. **************
  560.  
  561. ángulo TrazaVerificador (&ParedMedia)
  562.        ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯
  563. pila Buffer;
  564. {
  565. ComputaAngFinal(*ParedMedia.Bloque,*ParedMedia.Direc,&µ);    /*ø=ángulo de esquina final de pared*/
  566. Si µ>ø+Angß entonces µ=ø+Angß
  567. TrazarRayo(µ,&Buffer);
  568. Si Buffer.Bloque=*ParedMediaBloque entonces 
  569.     {
  570.     *ParedMedia.ßFinal=µ;
  571.     Punt++;            /*y SEGURO que pasaremos a la siguiente*/
  572.     devuelve(µ);         /*devuelve el último ß escaneado*/
  573.      }
  574.    sino {
  575.     InicPar=ComputaAngInicio(Pared[Punt].Bloque,Pared[Punt].Direc);
  576.     *ParedMedia.ßFinal=InicPar-ðß;
  577.     Punt++;
  578.     Pared[Punt].ßInicial=InicPar;
  579.     Pared[Punt].InicioTextura=0;
  580.     Pared[Punt].Bloque=Buffer.Bloque;
  581.     Pared[Punt].Direc=Buffer.Direc;
  582.     Pared[Punt].ZInicial=;
  583.  
  584.     ç=TrazaVerificador(&Pared[Punt]);
  585.     devuelve(ç);
  586.          }
  587.     /*Termina de Actualizar pared comenzada*/
  588.     CASE *ParedMedia.Direc OF
  589.         CASE Arriba entonces 
  590.             {
  591.               Dy=(*ParedMedia.By*256)-Oy;
  592.             Dx=Dy*Cotg(µ);
  593.             *ParedMedia.FinalTextura=Ox-(*ParedMedia.Bx*256)+Dx;
  594.             *ParedMedia.ZFinal=Dy*Cosec(µ);
  595.             }
  596.         CASE Abajo entonces 
  597.             {
  598.             Dy=((*ParedMedia.By+1)*256)-Oy;
  599.             Dx=Dy*Cotg(µ);
  600.             *ParedMedia.FinalTextura=((*ParedMedia.Bx+1)*256)-Ox+Dx;
  601.             *ParedMedia.ZFinal=Dy*Cosec(µ);
  602.             }
  603.         CASE Izquierda entonces 
  604.             {
  605.             Dx=((*ParedMedia.Bx+1)*256)-Ox;
  606.             Dy=Dx*Tg(µ);
  607.             *ParedMedia.FinalTextura=Oy-(*ParedMedia.By*256)+Dy;
  608.             *ParedMedia.ZFinal=Dx*Sec(µ)            
  609.             }
  610.         CASE SI_OTRO entonces    /*derecha*/ 
  611.             {
  612.             Dx=(*ParedMedia.Bx*256)-Ox
  613.             Dy=Dx*Tg(µ);
  614.             *ParedMedia.FinalTextura=((*ParedMedia.By+1)*256)-Oy+Dy;
  615.             *ParedMedia.ZFinal=Dx*Sec(µ);
  616.             }
  617.     END_CASE
  618. }
  619.  
  620. Refinemos la funcion que, dado un bloque, el observador, y una direccion, nos devuelve el angulo 
  621. formado por el rayo que "une" el observador, con el final de la pared impactada.
  622. NOTA: El angulo no sera uno cualquiera, sino uno de la serie ß.
  623.  
  624. **************
  625. *PSEUDOCODIGO*
  626. **************
  627.  
  628. ComputaAngFinal (Bloque,Direc,&angulo)
  629. ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯
  630. Case Direc of
  631. Case Arriba entonces {
  632.              OffsetX=(Bx+1)*256-Ox
  633.                OffsetY=By*256-Oy
  634.              }
  635. Case Abajo entonces {
  636.             OffsetX=Bx*256-Ox
  637.             OffsetY=(By+1)*256-Oy
  638.             }
  639. Case Izquierda entonces {
  640.             OffsetX=(Bx+1)*256-Ox
  641.                  OffsetY=(By+1)*256-Oy
  642.             }
  643. Case Derecha entonces {
  644.               OffsetX=Bx*256-Ox
  645.               OffsetY=By*256-Oy
  646.               }
  647. End_Case
  648.  
  649. Si OffsetX <> 0 entonces  *angulo=arctg(OffsetY/OffsetX)
  650.         sino Si OffsetY>0 entonces *angulo=90°
  651.                           sino *angulo=270°
  652.                           
  653.                                
  654. Ahora refinemos la funcion que, dado un bloque, el observador, y una direccion, nos devuelve el angulo 
  655. formado por el rayo que "une" el observador, con el principio de la pared impactada.
  656. NOTA: El ángulo devuelto pertenecera a la serie ß.
  657.  
  658. **************
  659. *PSEUDOCODIGO*
  660. **************
  661.  
  662. angulo ComputaAngInicio (Bloque,Direc,&angulo)
  663.        ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯
  664. Case Direc of
  665. Case Arriba entonces {
  666.              OffsetX=Ox-Bx*256
  667.                OffsetY=Oy-By*256
  668.              }
  669. Case Abajo entonces {
  670.             OffsetX=Ox-(Bx+1)*256
  671.             OffsetY=Oy-(By+1)*256
  672.             }
  673. Case Izquierda entonces {
  674.             OffsetX=Ox-(Bx+1)*256
  675.                  OffsetY=Oy-By*256
  676.             }
  677. Case Derecha entonces {
  678.               OffsetX=Ox-Bx*256
  679.               OffsetY=Oy-(By+1)*256
  680.               }
  681. End_Case
  682.  
  683. Si OffsetX <> 0 entonces  *angulo=arctg(OffsetY/OffsetX)
  684.         sino Si OffsetY>0 entonces *angulo=90°
  685.                           sino *angulo=270°
  686.                           
  687. Y como ya GOBLINS ha entrado en la frenetica dinamica de acabar la demo, esto va a ser lo ultimo que
  688. escriba sobre el tema. No esta todo, y sobran muchas cosas.En realidad el algoritmo implementado dista
  689. mucho de este doc, debido a las multiples modificaciones y optimizaciones, pero deberia servir para
  690. que cualquiera que se lo proponga, pueda comenzar a fabricar su propio algoritmo. Repito que este doc
  691. esta lleno de fallos y redundancias, y no es en absoluto implementable directamente. No os lo voy a
  692. dar todo ya digerido, hombres!. Pero pistas, teneis un monton, y seguro que mejoras tambien. Las 
  693. mejoras que encontreis, ya me las contareis, vale?.. 
  694. Bueno, ahora voy a ponerme a hacer el suelo mapeado... un saludillo...
  695.  
  696. PHORNEE/GOBLINS
  697.  
  698. Ah..!!.. y atentos a la proxima demo de GOBLINS, que se va a presentar en la Euskal Amiga Party III,
  699. y que se va a titular...
  700.  
  701. ..."EL OCASO DE UN PAYASO" (The down of the clown).... nos veremos alli...
  702.  
  703. PD: Cago en dios, tenemos que dejar el pabellon de AMIGA bien alto, joder, que van a ir peceros que
  704. controlan la ostia... a currar TODOS tios...